package dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class P104 {
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        List<Integer> total = new ArrayList<>(1);
        total.add(0);
        backTrack(nums, target, 0, total);
        return total.get(0);
    }

    void backTrack(int[] nums, int target, int nowSum, List<Integer> total) {
        if (target == nowSum) {
            total.set(0, total.get(0) + 1);
        } else if (nowSum < target) {
            for (int num : nums) {
                backTrack(nums, target, nowSum + num, total);
            }
        }
    }

    int dp(int[] nums, int target) {
        int len = nums.length;
        int[][] dp = new int[len][target];
        for (int num : nums) {
            dp[0][num] = 1;
        }
        //
        return 0;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{9};
        int target = 3;
        int result = new P104().combinationSum4(nums, target);
        System.out.println(result);
    }
}
